package 数据结构和算法.剑指offer.数组.数组中出现次数超过一半的数字;

import java.util.Arrays;

/**
 * 数组中出现次数超过一半的数字
 * <p>
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素
 * <p>
 * 本题有多种实现的思路。
 * 第一种就是使用java自带的数组排序，然后返回长度一半的数组即可
 * <p>
 * 第二种思路是摩尔投票法。算法的核心思想是正负抵消。由于众数出现的次数大于数组长度的一半，若记众数的票数+1，非众数的票数-1，则最后一定有所有的数字的票数和>0。设数组中nums中的众数为x，数组长度为n，若数组nums的前a个数字的票数和=0，则后(n-a)个数字的票数和一定还是>0。
 * <p>
 * 为构建正负抵消，假设数组首个元素 为众数，遍历统计票数，当发生正负抵消时，剩余数组的众数一定不变 （设真正的众数为x ）
 * <p>
 * ​ 当n1 = x ： 抵消的所有的数字中有一半是众数x。
 * <p>
 * ​ 当n1！=x：抵消的数字中少于或者等于一半是众数x
 * <p>
 * 利用此特性，每轮假设都可以缩小剩余数组区间，当遍历完成的时候，最后一轮假设的数字即为众数。
 */
public class Test {
    public int majorityElementOne(int[] nums) {
        Arrays.sort(nums);
        return nums[(nums.length) / 2];
    }

    // 摩尔投票法
    public int majorityElementTwo(int[] nums) {
        int x = 0;
        int votes = 0;
        for (int num : nums) {
            if (votes == 0) {
                x = num;
            }

            votes += num == x ? 1 : -1;
        }

        return x;
    }

}
